package linkedList.递归;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 重排链表143.java
 * @Description TODO https://leetcode-cn.com/problems/reorder-list/
 * @createTime 2021年03月12日 11:12:00
 */
public class 重排链表143 extends BaseLinkedListTest {
    /**
     * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
     * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
     * <p>
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * todo 1. 找到链表中点  2. 翻转右半部分链表 3 合并链表
     */

    public static void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        //todo 1. 找链表的中点 快慢指针
        ListNode fastPoint = head, slowPoint = head;
        while (fastPoint != null && fastPoint.next != null) {
            fastPoint = fastPoint.next.next;
            slowPoint = slowPoint.next;
        }
        //如果fastPoint不为null说明是奇数个节点，翻转的节点要往后一步
        ListNode temp=null;
        /*if (fastPoint!=null){
            slowPoint=slowPoint.next;
        }*/
        temp=slowPoint;
        //todo 2. 翻转右半部分链表
        ListNode rightNode = reverseNode(temp);
        //todo 3. 合并链表
        ListNode listNode = mergeTwoLists(head, rightNode);
        System.out.println(listNode);
    }

    private static ListNode mergeTwoLists(ListNode head, ListNode rightNode) {
        if (rightNode==null){
            return rightNode;
        }
        ListNode listNode = mergeTwoLists(head.next, rightNode.next);
        head.next=rightNode;
        rightNode.next=listNode;
        return head;
    }

    private static ListNode reverseNode(ListNode slowPoint) {
        if (slowPoint==null || slowPoint.next==null){
            return slowPoint;
        }
        ListNode node = reverseNode(slowPoint.next);
        slowPoint.next.next=slowPoint;
        slowPoint.next=null;
        return node;
    }

    public static void main(String[] args) {
        //ListNode listNode = mergeTwoLists(createLinkedList(1, 2, 3, 4), createLinkedList(7,6,5));

       reorderList(createLinkedList(1,2,3,4,5));
        //ListNode listNode = reverseNode(createLinkedList(1, 2, 3, 4, 5, 6, 7));
      // System.out.println(listNode);
    }
}
